#include <stdio.h>

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

void quick(int* a, int begin, int end)
{
  if(begin >= end)
    return;

  //选key
  int key = begin;
  int left = begin;
  int right = end;

  while(left < right)
  {
    //右边先走，找比key小的
    while(right > left && a[right] >= a[key])
    {
      right--;
    }

    //左边的再走，找比key大的
    while(right > left && a[left] <= a[key])
    {
      left++;
    }
    //大的数据向后走，小的向前来
    Swap(&a[left], &a[right]);
  }
  //使得key来到了正确的位置，并且以key划分了区间[left, key-1] key [key+1, end]
  Swap(&a[key], &a[left]);
  
  quick(a, begin, key-1);
  quick(a, key+1, end);
}

void quick1(int*a , int begin, int end)
{
  if(begin >= end) return;

  //挖坑法
  int left = begin, right = end;
  int key = a[left];
  int hole = left;

  while(left < right)
  {
    //还是right先走，找比key小的
    while(left < right && a[right] >= key)
    {
      right--;
    }
    a[hole] = a[right];
    hole = right;
    //left再走，找比key大的
    while(left < right && a[left] <= key)
    {
      left++;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key; 
  quick1(a, begin, hole-1);
  quick1(a, hole+1, end);
}

void quick2(int* a, int begin, int end)
{
  if(begin >= end) return;

  int key = begin;
  int prev = begin;
  int cur = begin;

  while(cur <= end)
  {
    while(a[cur] < a[key] && ++prev != cur)
    {
      //满足条件，进行交换
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }

  //每一次结束的最后一次交换
  Swap(&a[key], &a[prev]);

  quick2(a, begin, prev-1);
  quick2(a, prev+1, end);
}
void Test()
{
  int arr[] = {3,-1,1,2,4,5,8,7,6,9,-3};
  int sz = sizeof(arr) / sizeof(arr[0]);

 //quick(arr, 0, sz-1);
 // quick1(arr, 0, sz-1);
  quick2(arr, 0, sz-1);
  int i = 0;
  for(; i < sz; ++i)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}
int main()
{
  Test();
  return 0;
}
